package Algorithm.LinkedListExercise;

//判断单链表是否有环
public class linkedListTest01 {
    public static void main(String[] args) {
        Node node01 = new Node(1);
        Node node02 = new Node(5);
        Node node03 = new Node(6);
        Node node04 = new Node(7);
        Node node05 = new Node(8);
        Node node06 = new Node(9);
        Node node07 = new Node(1);
        node01.next = node02;
        node02.next = node03;
        node03.next = node04;
        node04.next = node05;
        node05.next = node06;
        node06.next = node07;
        node07.next = node05;
        System.out.println(function(node01));
    }

    public static void print(Node node) {
        while (node != null) {
            System.out.println(node.value);
            node = node.next;
        }
    }

    public static boolean function(Node head) {
        Node slow = head;
        Node fast = head.next;
        while (fast != null) {
            if (slow == fast) {
                System.out.println(slow.value);
                return true;//当两个指针重逢时，说明存在环，否则不存在。
            }
            slow = slow.next;  //每次迭代时，指针1走一步，指针2走两步
            fast = fast.next.next;
            if (fast == null) return false;//不存在环时，退出
        }
        return true; //如果tmp2为null，说明元素只有一个，也可以说明是存在环
    }
}

class Node {
    Object value;
    Node next;

    Node(Object value) {
        this.value = value;
        this.next = null;
    }
}
